package solution;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2021-10-07 11:23
 */
public class Solution_6DP_package {

    /*===========================================================================================================================
     *DP 背包问题  0-1背包
     * 给你一个可装载重量为 `W` 的背包和 `N` 个物品，每个物品有重量和价值两个属性。其中第 `i` 个物品的重量为 `wt[i]`，价值为 `val[i]`，
     * 现在让你用这个背包装物品，最多能装的价值是多少？
     * `dp[i][w]` 的定义如下：对于前 `i` 个物品，当前背包的容量为 `w`，这种情况下可以装的最大价值是 `dp[i][w]`。最终答案就是 `dp[N][W]`
     * dp[i][j]=dp[i-1][j];背包容量够
     * dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-wt[i]]+val[i]);背包容量够
     *  */
    int knapsack(int W, int N, int[] wt, int[] val) {
        int[][] dp=new int[N+1][W+1];
        //dp[0][...]=0,dp[...][0]=0
        for (int i = 0; i <= N; i++) {
            dp[i][0]=0;
        }
        for (int i = 0; i <=W ; i++) {
            dp[0][i]=0;
        }
        for (int i = 1; i <=N ; i++) {
            for (int j = 1; j <=W ; j++) {
                if (j-wt[i-1]<0){
                    //背包装不下第i个物品
                    dp[i][j]=dp[i-1][j];
                }else {
                    //背包可以装得下，选择装或者不装
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-wt[i-1]]+val[i-1]);
                }
            }
        }
        return dp[N][W];
    }

    /*===========================================================================================================================
     *DP 背包问题 子集背包 416. 分割等和子集
     * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     * dp[i][j] = x 表示，对于前 i 个物品，当前背包的容量为 j 时，若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满。
     *  */
    public boolean canPartition1(int[] nums) {
        //背包容量为sum/2
        int sum=0;
        for (int ns:nums) {
            sum+=ns;
        }
        if (sum%2==1)return false;
        sum=sum/2;
        int n=nums.length;
        boolean[][] dp=new boolean[n+1][sum+1];
        //dp[0][...]=false（没有物品可以选择）,dp[...][0]=true(背包容量为0，则不装即为一种方式)
        for (int i = 0; i <= n; i++) {
            dp[i][0]=true;
        }
        for (int i = 0; i <=sum ; i++) {
            dp[0][i]=false;
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=sum ; j++) {
                if (j-nums[i-1]<0){
                    //背包不足
                    dp[i][j]=dp[i-1][j];
                }else {
                    //背包足够装，装入或不装入背包
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][sum];
    }

    /*状态压缩
     * 唯一需要注意的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。
     * */
    public boolean canPartition(int[] nums) {
        //背包容量为sum/2
        int sum=0;
        for (int ns:nums) {
            sum+=ns;
        }
        if (sum%2==1)return false;
        sum=sum/2;
        int n=nums.length;
        boolean[] dp=new boolean[sum+1];
        //dp[0][...]=false（没有物品可以选择）,dp[...][0]=true(背包容量为0，则不装即为一种方式)
        Arrays.fill(dp,false);
        dp[0]=true;
        for (int i = 1; i <=n ; i++) {
            for (int j = sum; j >=0 ; j--) {
                if (j-nums[i-1]>=0){
                    //背包足够装，装入或不装入背包
                    dp[j]=dp[j]||dp[j-nums[i-1]];
                }/*else {
                    //背包不足
                    dp[j]=dp[j];
                }*/
            }
        }
        return dp[sum];
    }

    /*===========================================================================================================================
     *DP 背包问题 完全背包 518. 零钱兑换 II
     * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
     * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。
     * dp[i][j] 的定义若只使用 coins 中的前 i 个硬币的面值，若想凑出金额 j，有 dp[i][j] 种凑法。
     * dp[0][..] = 0， dp[..][0] = 1
     * dp[i][j]=  dp[i-1][j]，不使用 coins[i] 这个面值的硬币，那么凑出面额 j 的方法数
     * dp[i][j]=dp[i][j-coins[i-1]]，使用 coins[i] 这个面值的硬币
     *  */
    public int change(int amount, int[] coins) {
        //背包容量w为amount，可选择的个数为n，coins表示价值列表
        int n=coins.length;
        int[][] dp=new int[n+1][amount+1];
        //dp[0][...]=0,dp[...][0]=1
        for (int i = 0; i <= n; i++) {
            dp[i][0]=1;
        }
        for (int i = 0; i <=amount ; i++) {
            dp[0][i]=0;
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=amount ; j++) {
                if (j-coins[i-1]<0){
                    dp[i][j]=dp[i-1][j];
                }else {
                    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[n][amount];
    }
    /*状态压缩*/
    public int change1(int amount, int[] coins) {
        int[] dp=new int[amount+1];
        dp[0]=1;
        for (int coin:coins) {
            for (int i = coin; i <=amount ; i++) {
                dp[i]+=dp[i-coin];
            }
        }
        return dp[amount];
    }

}
